/*Copyright (c) Microsoft Open Technologies, Inc.  All rights reserved.
Microsoft Open Technologies would like to thank its contributors, a list
of whom are at http://rx.codeplex.com/wikipage?title=Contributors.

Licensed under the Apache License, Version 2.0 (the "License"); you
may not use this file except in compliance with the License. You may
obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
implied. See the License for the specific language governing permissions
and limitations under the License.*/

// Problem:
//     #Google interview question# Giving a google searching log, design an algorithm to find out
//     a most popular searching keyword which exists more than a half of the whole set
//     Restriction: Space complexity O(1); algorithm complexity O(n)
// Solution:
//     http://www.cppblog.com/everyday/archive/2013/07/02/201473.html
//
// Author: everyday (weijie.he@live.com)
//

#include <iostream>
#include <string>
#include "Suite.h"
#include "Test.h"

using namespace TestSuite;

// Get the most popular searching keyword in Google. :)
template<typename T>
T get_most_popular_keyword(const T *list, int size) {
    T result = list[0];
    int count = 0;

    for (int i=0; i<size; i++) {
        if (list[i] == result)
            count++;
        else {
            if (--count == 0) {
                count = 1;
                result = list[i];
            }
        }
    }

    return result;
}

#define build_test(arr, expectation) (get_most_popular_keyword(arr, sizeof(arr) / sizeof(arr[0])) == expectation)

class algorithm_test : public Test {
public:
    void run() {
        test_instance();
    }

private:
    void test_instance() {
        int list[] = { 1, 3, 1, 1, 1, 1, 2, 1, 6, 1, 1, 3, 0, 4, 1, 3};
        test_(build_test(list, 1));

        int list2[] = { 1, 1, 1, 1, 2, 2, 2 };
        test_(build_test(list2, 1));

        int list3[] = { 2, 2, 2, 2, 2, 1, 1, 1 };
        test_(build_test(list3, 2));
    }
};

int main() {
    Suite suite("get_most_popular_keyword tests");
    suite.addTest(new algorithm_test());
    suite.run();

    return suite.report();
}